// 首先封装节点
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

// 封装链表
class LinkedList {
  constructor() {
    // head是个空的节点元素
    this.head = null;
    this.length = 0;
  }

  // 给链表尾部添加一个新的项
  append(data){
    const newNode = new Node(data);
    //2. 追加到新节点
    if (this.length === 0) {  //空链表
      this.head = newNode;
    } else {
      let current = this.head;
      while(current.next != null){
        current = current.next;
      }
      current.next = newNode;
    }
    this.length++;
  }

  //在列表某位置插入某元素
  insert(position, data){
    // 1. 首先判断越界问题
    if (position < 0 || position > this.length) return false;
    // 2.创建新的节点
    const newNode = new Node(data);
    // 3.插入元素
    if (position === 0) {
      newNode.next = this.head;
      this.head = newNode;
    } else {
      let index = 0;
      let current = this.head;
      let previous = null;
      while(index++ < position) {
        previous = current;
        // 已经指向要推后的节点元素
        current = current.next
      }
      previous.next = newNode;
      newNode.next = current;
    }
    this.length++;
    return true
  }

  // 获取对应位置元素
  get(position){
    // 1. 首先判断越界问题
    if (position < 0 || position > this.length -1 ) return false;
    // 2. 查找该位置的元素
    let index = 0;
    let current = this.head;
    while(index++ < position){
      current = current.next;
    }
    return current.data
  }

  // 返回元素在列表中的索引
  indexOf(data) {
    let current = this.head;
    let index = 0;
    while(current) {
      if(current.data === data) {
        return index;
      }
      index++;
      current = current.next;
    }
    return -1;
  }

  //删除指定位置元素
  remove(position) {
    // 1. 首先判断越界问题
    if (position < 0 || position > this.length -1 ) return null;
    // 2.删除元素
    let current = this.head;
    let previous = null;
    let index = 0;
    if (position === 0) {
      this.head = current.next;
    } else {
      while (index++ < position){
        previous = current;
        current = current.next;
      }
      previous.next = current.next;
    }
    this.length--;
  }

  //修改某个位置的元素
  update(position, data){
    // 1. 首先判断越界问题
    if (position < 0 || position > this.length -1 ) return false;
    // 2.查找位置并修改data
    let current = this.head;
    let index = 0;
    while (index++ < position){
      current = current.next;
    }
    current.data = data
  }

  //给你data你去找他并且删掉
  removeData(data){
    // 获取某元素位置
    const index = this.indexOf(data);
    // 删除某个位置
    if (index === -1) return;
    this.remove(index);
  }

  //是否为空
  isEmpty() {
    return this.length === 0;
  }

  // 包含元素个数
  size() {
    return this.length;
  }
}

class DoublyNode extends Node {
  constructor(data) {
    super(data);
    this.prev = null;
  }
}

class DoublyLinkedList extends LinkedList{
  constructor() {
    super();
    this.tail = null;
  }

  // 重写append
  append(data){
    // 1.根据元素创建
    const newNode = new DoublyNode(data);
    // 2. 追加元素
    // 如果链表为空
    if (this.length === 0) {
      this.head = newNode
      this.tail = newNode;
    } else {
      // 找到最后一个节点
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
    this.length++
  }

  //在某个位置插入元素
  insert(position, data){
    //创建一个节点
    const newNode = new DoublyNode(data);
    if (position < 0 || position > this.length) return false;
    // 位置在第一个 判断是否是空链表
    if (position === 0) {
       if (this.head === null) {
         this.head = newNode;
         this.tail = newNode;
       } else {
         newNode.next = this.head;
         this.head.prev = newNode;
         this.head = newNode;
       }
    }else if (position === this.length){
      newNode.prev = this.tail;
      this.tail.next = newNode;
      this.tail = newNode;
    } else {
      let index = 0;
      let current = this.head;
      while(index++ < position) {
        current = current.next;
      }
      newNode.next = current.next;
      newNode.prev = current.prev;
      current.prev.next = newNode;
      current.prev = newNode;
    }
    this.length++;
    return true;
  }

  //删除指定位置元素
  remove(position){
    if (position < 0 || position > this.length - 1) return false;

    let current = this.head;
    if (position === 0) {
      if (this.length === 1) {
        this.tail = null
        this.head = null
      } else {
        this.head = this.head.next;
        this.head.prev = null;
      }
    } else if (position === this.length-1){
      current = this.tail; // 因为下面修改指针会改变指针的信息
      this.tail.prev.next = null;
      this.tail = current.prev;
    } else {
      let index = 0;
      let previous = null;
      while (index++ < position) {
        previous = current;
        current = current.next
      }
      previous.next = current.next;
      current.next.prev = previous;
    }
    this.length--;
    return true;
  }

  // 更新某位置节点信息
  // update(position, data) 修改指定位置的节点
  // 重写 update()
  update(position, data) {
    // 1、删除 position 位置的节点
    const result = this.remove(position);
    // 2、在 position 位置插入元素
    this.insert(position, data);
    return result;
  }

  removeData(data) {
    const index = this.indexOf(data);
    if (index === -1) return;
    this.remove(index);
  }
}

const doublyList = new DoublyLinkedList();
doublyList.append("aaa")
doublyList.append("bbb")
doublyList.append("ccc")
console.log(doublyList);
doublyList.insert(2,0)
console.log(doublyList);
doublyList.update(0,'new');
console.log(doublyList);